.NEWSS (DATA STRUCTURES,DATA STRUCTURES) <<REVISED>>
.DAT:NEWSSS DATA TYPES

	In this section we present the data types available in
'AL.  Roughly speaking, a %4data type%* is a kind of numeric object.
For example, FORTRAN has the data types INTEGER and REAL.  A %4variable%*
is an identifier which can take on %4values%*.  In 'AL, each variable must
be %4declared%*, that is, one must state what its type is,
somewhere in the program before it is used.
There are several reasons for this:
It allows the compiler to detect spelling errors,
and it allows the same name to be used in different blocks without
conflict.  'AL uses ALGOL block structure,
which means that all variables declared between a particular BEGIN and
END are accessible only to code which appears between the same BEGIN-END
pair.


.NEWSSS	ALGEBRAIC DATA TYPES: SCALARS

	Algebraic data types are the most familiar.  They represent
measurements in the real world.  An algebraic variable can assume
a value by means of the %4assignment statement%*, which consists
of the variable name, a left arrow ("α←"), and an expression which has the
correct type.
When an assignment statement is executed, the expression on the right
hand side is evaluated, and that value replaces the old value of the
variable on the left hand side.

	The most elementary data type is  %4simple%*,   which is  internally
represented  as  a floating-point  number.   Simples  are  used 
for dimensionless scalar quantities, like the number of times some operation
is to be repeated, or to implement a  signal which becomes positive when some
critical operation is finished.
The arithmetic operations available on simple variables are addition,
subtraction, multiplication, and division; the arithmetic operators which
perform these operations are the standard: +, -, *, /.  As is usual in
algebraic languages, the first two have lower precedence than the  others.

	Simple constants are written as (base ten) numbers, either with
or without a decimal point and fractional part.
Here are some examples of declarations and applications of simple variables:
.unfill
	SIMPLE S1, S2; α{Our examples will use this rather stupid
		scheme for naming variables, just to clarify what the
		type of each entity is.  Please understand that 
		identifiers can be any string of letters, of any 
		length.α}
	S1 α← 2;
	S2 α← 3.74;
	S1 α← S2 * (S1 - 3.2);
.REFILL

	Often it is desirable to give some physical meaning to scalar
variables.  'AL provides
for variables with these special types:  %4time, distance, angle,%*
 and %4mass%*.
Time constants are just like simple constants, except they are multiplied
by the reserved word %4sec%* (for "seconds").  The other reserved words
related to these "dimensioned" data types are %4cm%* (centimeters),
%4deg%* (degrees) and
 %4gm%* (grams).

	Dimensioned scalars are used exactly in the same way
as simple scalars; the only difference is that 'AL will check to assure
that addition and subtraction are only performed on compatible values.
'AL performs type checking for each arithmetic operation and
each assignment.  Addition, subtraction, and assignment require exact
type match; multiplication and division do not, but produce a result
of a type usually different from that of the arguments; this new type
is then propagated through the expression.  In this way, intermediate
results can be of types not declared.  This causes no problem unless
one tries to use such results in an assignment.
The only exception to the type checking rules
is that simple scalars are automatically converted to any other
type if necessary to maintain type consistency.

	Here are some examples of dimensioned scalars:
.UNFILL
	TIME TM1, TM2;
	MASS MS1;
	ANGLE THETA, PHI;

	TM1 α← 3 * SEC;
	MS1 α← MS1 + 2.2 * GM;
	MS1 ← MS1 + 2.2;  α{The constant 2.2 will be automatically
		converted to grams.α}
	THETA α← 90 * DEG;
	TM1 α← TM2 * 5.5;
	PHI α← THETA * 4 * DEG;  α{This is a mistake;
		the right side has type %4deg*deg%*α}
.REFILL

	If the user feels more comfortable with inches or pounds, it
is quite easy to write macros which will make such usage possible.
This is best demonstrated by example:
.UNFILL
	DEFINE INCHES = "(2.54 * CM)";
	DEFINE FEET = "(12 * INCHES)";
	DEFINE LB = "(GM * 1000 / 2.2)";

	MS1 ← 2.2*LB;  α{= 1000*GMα}
	DS1 ← 3*FEET;  α{= 3*12*2.54*CMα}
.REFILL

	The user may wish to create new dimensioned scalars, such
as forces or velocities.  This is readily done by means of the
%4dimension%* statement and a few macros.  This shows how:
.UNFILL
	DIMENSION FORCE = DISTANCE*MASS/(TIME*TIME);
	DEFINE DYNES = "(GM*CM/(SEC*SEC))";
	DIMENSION VELOCITY = DISTANCE/TIME;
	DEFINE CPS = "(CM/SEC)";

	FORCE FO1;
	VELOCITY VL1;
	VL1 ← 2.3*CPS;
	FO1 ← VL1 * 3 * GM / (8.4 * SEC);
.REFILL

.NEWSSS OTHER ALGEBRAIC DATA TYPES
	Scalars are insufficient to describe all measurements of interest
to the user of 'AL.  We turn now to other algebraic
data types.  They are syntactically much like scalars:  they are declared
and can enter into arithmetic expressions and assignments.

	The world in which 'AL resides has three dimensions.
We impose a Euclidean structure on that space by setting up three
cardinal, orthogonal axes, which meet at the origin.
The actual alignment of these "table" axes will, in general, depend
on the particular work station involved; it is expected, however,
that the positive Z axis will point upwards (this is not at all
crucial).

	The first data type we will discuss is the %4vector%*.  It represents
either a translational offset or a location.  The latter 
meaning is the result of
translating the null vector, that is, the origin of the coordinate system.

It is possible to "stretch" or "shrink" vectors by multiplying and
dividing them by scalars.  There are these operations on two vectors:
addition, subtraction, and dot product (using +, - and .).
If the two vectors are, say, 
.UNFILL
	V1=VECTOR(X1,Y1,Z1) and V2=VECTOR(X2,Y2,Z2),

then we have

	S*V1 = VECTOR(S*X1,S*Y1,S*Z1)
	V1+V2 = VECTOR(X1+X2,Y1+Y2,Z1+Z2)
	V1-V2 = VECTOR(X1-X2,Y1-Y2,Z1-Z2)
	V1.V2 = X1*X2 + Y1*Y2 + Z1*Z2    .
.REFILL

Thus, addition
and subtraction produce vectors in the familiar way; the dot product
is the sum of the products of the three coordinates and has type
%4distance*distance%*.  The magnitude of
a vector is calculated by the function ABS, which returns
a scalar of type distance.

	Vectors can be constructed out of three distance expressions
by means of the function VECTOR.  Since simple expressions can be
coerced into distance expressions, simple expressions suffice.
To extract the components of a vector, take dot products with
the cardinal axes.

	There are three predeclared vectors in 'AL; they are the 
cardinal axes of the coordinate system:
.UNFILL
	VECTOR X, Y, Z; α{These are predeclared and have values as followsα}
	X α← VECTOR(1,0,0);
	Y α← VECTOR(0,1,0);
	Z α← VECTOR(0,0,1);
.REFILL
Here are examples of other vectors:
.UNFILL
	VECTOR V1, V2, V3;
	SIMPLE S1;
	DISTANCE D1;

	D1 α← 4 * CM;
	S1 α← -2;
	V1 α← VECTOR(S1, 2.3, D1);
	S1 ← V1 . Y;  α{So S1 gets 2.3α}
	V2 α← V1 / S1;  α{So V2 ← VECTOR(-2/2.3, 1, 4/2.3).}
	V3 ← S1 * V2;  α{So V3 ← V1α}
	S1 ← ABS(V1) + V2.V3; α{This is a type mismatch!α}
.REFILL
	The %4rot%*, our next data type,
represents either a rotational offset or an orientation.
The latter is the result of applying the
rotation to the fundamental coordinate system.
Rots are internally stored as 3x3 matrices, which operate on
column vectors in the usual way.  Thus
rots can operate on vectors and move them around
the origin (without changing their length); they can also operate
on other rots (by matrix multiplication).
To rotate a vector (about the table origin), multiply
the vector (on the right) by the rot (on the left).  To compose
rots, multiply them together; the one on the right will be
applied first.

A rotation can be constructed with the function ROT, which takes
two arguments:  a vector, which is to be the axis of rotation, and 
an angle, which is the amount to rotate.
This turns out to be a general representation far easier to
write and understand than raw matrices.  We hope the following
examples will serve to clarify the proper use of rots:
.UNFILL
	ROT R1, R2, R3;
	ANGLE ALPHA, BETA, GAMMA;
	R1 α← ROT(X, 90*DEG);
	V1 ← R1 * Z;  
.COMT 12
		α{V1 gets Z rotated 90 degrees about X, so V1 α← VECTOR(0,-1,0).α}
.END
	R2 α← ROT(Y, 45*DEG);
	R3 α← R2 * R1; 
.COMT 12
	    α{Thus, R3 means:  rotate first 90 degrees about the X axis,
		then 45 about the original Y axis.α}
.END

	R1 ← ROT(X,ALPHA);
	R2 ← ROT(R1*Y,BETA);
	R3 ← ROT(R2*Z,GAMMA);
	R4 ← R3 * R2 * R1;
.COMT 12
		α{R4 is then a rotation with this meaning:
		Rotate by alpha degrees about the X axis, then by
		beta degrees about the new Y axis, then by gamma
		degrees about the doubly new Z axis.α}
.END
.REFILL
	The next data type is the
%4frame%*, used to represent a coordinate system.  It has
two components: the location of the origin (a vector) and the orientation
of the axes (a rot).  Frames are typically used to describe objects;
one can specify locations of features on an object by translating them
from the object's origin.

	There are several predeclared frames in 'AL.  %4Table%*
is the frame which represents the work station's frame of reference.
Each hand available to the system also has a frame variable, whose
value (continually updated)
is the position of that hand.  Currently, there are two such
frames:  %4yellow%* and %4blue%*.  Each arm has a rest, or
park position, known as %4ypark%* and %4bpark%*.

	A frame may be constructed by a call 
on the function FRAME,
which takes two arguments: a vector (for the position) and a rot (for
the orientation). To extract the vector or the rot from a frame,
use the functions LOC and ORIENT, respectively.
To find where a vector goes if its base is moved from the table
to the coordinate system of some frame, "multiply" the frame (on
the left) by the vector (on the right).
  Often one wants to
construct a vector which is oriented like, say, the X vector in
some frame, say F1.  The %4with respect to%* operator gives exactly
that; one writes (X#WRT#F1).  Examples of this and other constructs
pertaining to frames follow.
.UNFILL
	FRAME F1, F2, F3;
	F1 ← FRAME(2*X, ROT(Z,90*DEG);
		α{F1 sits 2 centimeters from the table, in the X
		direction.  Its coordinate system has X where the
		table's Y points.α}
	V1 ← X WRT F1;
		α{This evaluates to VECTOR(0,1,0)α}
	V1 ← F1 * Y;
		α{This evaluates to VECTOR(0,0,0)α}
	V2 ← V3 WRT F2;
		α{This is equivalent to (F2*V3) - LOC(F2)α}
.REFILL
	Next we have the %4plane%*, used to separate space into regions and
to specify the locus of searches.  Planes are formed by use of the
function PLANE, which takes two vectors as arguments:  The plane
is to pass through the first vector, and the outward-facing normal
to the plane is in the direction of the second vector.  
Thus PLANE(X,Y) is a plane parallel to the X-Z plane, translated
from it by one centimeter in the X direction.

Planes are internally stored by four numbers: the first three 
are an outward-facing normal, and the last is the opposite of the
distance from the plane to the origin.  

Each
plane divides space into three regions: inside, on, and outside the
plane.  (The last set contains all points on the side of the plane
towards the outward-facing normal, for instance.)
To find out in which region a point (represented by a vector) lies,
extract the inner product of the vector with the plane.  
 Its value is a distance scalar whose absolute value  is the shortest
distance from the  vector to the plane, and whose sign is negative if
the vector is inside the plane, 0 if the vector is on the plane,  and
positive if the vector is outside the plane.
The arithmetic operator for the inner product is a dot; the plane must
appear on the left of the dot and the vector on the right.
If the plane P has internal representation with four numbers A, B, C, 
and D, then we have:
.UNFILL
	P.V = A*X1 + B*X2 * C*X3 + D
.REFILL

Other operations available on planes are translation (by adding a vector)
and rotation (by multiplying by a rotation).
To get the outward-facing normal of a plane, use the function NORMAL,
which takes a plane argument and returns a vector.

Examples:
.UNFILL
	PLANE P1, P2;
	P1 ← PLANE(VECTOR(0,0,0),Z);
		α{This is the surface of the tableα}
	V1 ← NORMAL(P1 + V2);
		α{No matter what V2 is, V1 will get Zα}
	DS1 ← P1 %5.%* VECTOR(2, -13.2, 32.3);
		α{DS1 gets 32.3*cmα}
.REFILL
	The last of the algebraic data types is the %4trans%*, which
stands for "transform".  It is an operator, that is, a function, which
can operate on vectors, frames, and planes.  The application of a
trans to any of these is written as if it were a multiplication, with
the trans on the left.  To compose several transes together, "multiply"
them, with the one to be applied first on the right.

	The trans itself is defined as a function which can take objects
in one frame of reference into another.  One can construct a trans
by use of the function TRANS, which takes two arguments: a vector
(the translational part) and a rotation (the rotational part).  The
application of a trans to a vector, frame, or plane first rotates that
object according to the rotation part (rotating about the table origin),
and then translates the result according to the translational part.
   When a  frame is used  in a context  demanding a
transformation,   it will be understood as  a shorthand for the trans
leading from the table; thus we see that the expression F1*V1 is really
the application of the trans "TABLEα→F1" to the vector.

	There is another convenient way to specify a trans: by forming
it from two frames.  The trans is then the function which takes the
origin of the first frame across to the origin of the second, performing
a rotation first to get the axes aligned.  This method of specifying
a trans is accomplished by use of the arithmetic operator "α→".

	Examples:
.UNFILL
	TRANS T1, T2;
	T1 α← F1α→F2;
		α{Thus T1*F1 = F2α}
	V1 α← T1*V2;
	T2 α← T1*T1;
	V1 ← F1*V2;  α{Equivalent to (TABLE→F1)*V2α}
.REFILL
.NEWSSS PLANNING VALUES
	'AL works under the fundamental philosophy that arm motions
should be planned in advance.  Since an arm trajectory cannot be
calculated reasonably unless the end-points (and any specified intermediate
points) are known fairly accurately, it is necessary that the compiler
maintain for each variable a %4planning value%* which may be used in
the case that the variable enters into a motion specification.  We will
not discuss here the results of poor values at planning time; that has
been well covered earlier.  What is of importance is that the compiler
assigns to each variable a planning value at each statement in the program.

	Initially, the planning value of each variable is "undefined"; one
of the ways that a planning value can be assumed is through an assignment
statement.  The compiler evaluates the planning value of the right hand side,
and this becomes the new planning value of the variable on the left.

	Propagating the planning value across loops is complicated; in the
case that the variable can take multiple values, the compiler either
sets the planning value to "undefined" or, as 'AL becomes more advanced,
maintains parallel "worlds" in which each planning value is monovalued.

	Variables can attain different values at run-time than their planning
values when some real-world measurement is taken and the result used in an
arithmetic expression.  The most common example of this is that the frames
YELLOW and BLUE are always kept accurate at run-time by feedback from the
arm hardware, so their values will in general differ from those planned.

	There is an arithmetic operator which, when applied to any variable
or expression
returns its planning value.  This is the hash mark ("α#").  Expressions such
as α#(FROB) or α#(3#*#S1) always evaluate to constants; repeated application
of the hash operator is, in effect, ignored.

	There is one other way to affect the planning value of a variable,
and that is by the %4pseudo-assignment%* statement.  This looks just like
an assignment statement, except the operator is a double left arrow ("α←α←").
The right-hand side of the statement is evaluated, and
this becomes the planning value of the left-hand side.  Note that
for all the data types so far discussed, it is essential that the
expression on the right hand side be either a constant or made up
solely of constants; the compiler will not assume the presence of 
the planning value operator if it is missing.

Here is an example of a loop, showing what planning values obtain
at various places:

.UNFILL
.begin
.narrow 8,8
SIMPLE A, B, C;
A  α← 1;
B  α← 1;
C  α← 1;
WHILE <condition> DO
	BEGIN
	α{α#(A)=1, α#(B)=UNDEFINED, α#(C)=UNDEFINEDα}
	B α← 3;
	α{α#(A)=1, α#(B)=3, α#(C)=UNDEFINEDα}
	C ←← α#(B);
	B α← 4;
	α{α#(A)=1, α#(B)=4, α#(C)=3α}
	END;
α{α#(A)=1, α#(B)=UNDEFINED, α#(C)=UNDEFINEDα}
.end
.REFILL

.arith: NEWSSS	ARITHMETIC

	Here is  a summary of  the arithmetic  expressions available.
They  are grouped by the  type of their values.   These abbreviations
are used: `s' = scalar, `v' = vector, `r' = rot, `f' = frame, `p' = plane,
`t' = trans.
%7
.BEGIN VERBATIM
.GROUP
scalar expressions:
s + s		scalar addition (commutative)
s - s		scalar subtraction
s * s		scalar multiplication (commutative)
s / s		scalar division
v . v		dot product of two vectors (commutative)
p . v		signed distance from vector to plane (see discussion
			above on planes)

.MAYBREAK
vector expressions:
s * v		dilation of a vector
v / s		contraction of a vector
v + v		vector addition (translation of the first vector by 
			the second) (commutative)
v - v		vector subtraction
r * v		rotation of a vector
t * v		transformation of a vector
v WRT f		a vector of length ABS(v) rotated into f's system; like
			ORIENT(f)*v; that is, a vector in table
			coordinates which looks to the table as v
			does to f.
.MAYBREAK
rot expressions:
r * r		composition of two rots (first to be applied is on the 
			right)

.MAYBREAK
frame expressions:
t * f		transformation of a frame

.MAYBREAK
plane expressions:
p + v		translation of a plane by a vector
r * p		rotation of plane (about table origin)
t * p		transformation of a plane by a trans

.MAYBREAK
trans expressions:
f → f		transformation which leads from the first frame to
			the second
t * t		composing two transes.  The one on the right will operate
			first.

.MAYBREAK
PREDECLARED CONSTANTS AND VARIABLES:

π is simple, has value = 3.14159...
TABLE is a frame which has standard table coordinates. (constant)
BLUE is the location of the blue hand.
YELLOW is the location of the yellow hand.
BPARK is where the blue hand parks. (constant)
YPARK is where the yellow hand parks. (constant)
X is VECTOR(1,0,0).
Y is VECTOR(0,1,0).
Z is VECTOR(0,0,1).
.END
%*

Any expression preceeded with the symbol "α#" means "the planning value
of this expression", that is, a constant is substituted for the entire
expression in the expander.
.UNFILL

EXTRACTION FUNCTIONS:

LOC(FRAME) is a vector whose value is the location of the frame.
ORIENT(FRAME) is a rot whose value is the orientation of the frame.
NORMAL(PLANE)	is the outward facing normal vector of a plane.
.REFILL

.NEWSSS	SOME EXAMPLES OF ARITHMETIC EXPRESSIONS
.UNFILL
In the following examples, assume these declarations:
FRAME F1, F2, etc;
VECTOR V1, V2, etc;
SIMPLE S1, S2, etc;
ROT R1, R2, etc;
PLANE P1, P2, etc;

.MAYBREAK
F1'S unit Y vector, in TABLE coordinates:
	F1 * Y

.MAYBREAK
F1's Z vector as seen from F2:
	(F2α→F1) * Z

.MAYBREAK
A vector pointing in same direction as F1's X coordinate:
	X WRT F1

.MAYBREAK
V1 rotated 90 degrees about the table's Z axis:
	ROT(Z,90*DEG)*V1

.MAYBREAK
F1's Y-Z plane:
	PLANE(LOC(F1),X WRT F1)

.MAYBREAK
A plane 3 centimeters above the table:
	PLANE(VECTOR(0,0,3),Z);
	PLANE(3*Z,Z);

.MAYBREAK
An identity with WRT:
	V1 WRT F1 = ORIENT(F1)*V1 = (F1*V1) - LOC(F1)
.REFILL